#include <lcthw/list_algos.h>
#include <lcthw/dbg.h>

inline void ListNode_swap(ListNode *a, ListNode *b)     // Function to swap the values in two nodes
{
    void *temp = a->value;
    a->value = b->value;
    b->value = temp;
}

// Bubble sort algorithm
int List_bubble_sort(List *list, List_compare cmp)
{
    int sorted = 1;                                     // Initialize the sorted flag to 1, meaning the list is not fully sorted

    if(List_count(list) <= 1)                           // If the list has 0 or 1 elements, return 0, meaning the list is sorted
        return 0;                                       

    do
    {
        sorted = 1;                                     // Set the sorted flag to 1

        LIST_FOREACH(list, first, next, cur)            // Loop through the list
        {
            if(cur->next)                               // If there is a next node
            {
                if(cmp(cur->value, cur->next->value) > 0) // If the current value is greater than the next value
                {
                    ListNode_swap(cur, cur->next);      // Swap the values of the current and next nodes
                    sorted = 0;                         // Set the sorted flag to 0
                }
            }
        }
    } while(!sorted);                                   // Continue until the list is sorted

    return 0;
}   

// Merge function
List *List_merge(List *left, List *right, List_compare cmp)
{
    List *result = List_create();                       // Create a new list for the result
    check_mem(result);                                  // Check if the result list was created

    while(List_count(left) > 0 || List_count(right) > 0) // Loop while the left or right list has elements
    {
        if(List_count(left) > 0 && List_count(right) > 0) // If both lists have elements
        {
            if(cmp(List_first(left), List_first(right)) <= 0) // If the first element of the left list is less than or equal to the first element of the right list
            {
                List_push(result, List_shift(left));     // Push the first element of the left list to the result list
            }
            else
            {
                List_push(result, List_shift(right));    // Push the first element of the right list to the result list
            }
        }
        else if(List_count(left) > 0)                   // If only the left list has elements
        {
            List_push(result, List_shift(left));         // Push the first element of the left list to the result list
        }
        else
        {
            List_push(result, List_shift(right));        // Push the first element of the right list to the result list
        }
    }

    return result;                                      // Return the result list

error:
    return NULL;
}

// Merge sort algorithm
List *List_merge_sort(List *list, List_compare cmp)
{
    List *left;                                         // Declare a list for the left half of the list
    List *right;                                        // Declare a list for the right half of the list
    int middle = List_count(list) / 2;                  // Calculate the middle index of the list

    if(List_count(list) <= 1)                           // If the list has 0 or 1 elements
        return list;                                    // Return the list

    left = List_create();                               // Create a new list for the left half
    right = List_create();                              // Create a new list for the right half
    check_mem(left);                                    // Check if the left list was created
    check_mem(right);                                   // Check if the right list was created

    LIST_FOREACH(list, first, next, cur)                // Loop through the list
    {
        if(middle > 0)                                  // If the middle index is greater than 0
        {
            List_push(left, cur->value);                // Push the value of the current node to the left list
        }
        else
        {
            List_push(right, cur->value);               // Push the value of the current node to the right list
        }

        middle--;                                       // Decrement the middle index
    }

    left = List_merge_sort(left, cmp);                  // Recursively sort the left half
    right = List_merge_sort(right, cmp);                // Recursively sort the right half

    return List_merge(left, right, cmp);                // Merge the left and right halves

error:
    if(left) List_destroy(left);                        // Destroy the left list
    if(right) List_destroy(right);                      // Destroy the right list

    return NULL;
}